package vip.liux.backend.infrastructure.algorithm;

public class Sort {

    public static final int[] ARRAY = {5, 2, 9, 1, 5, 6};

    /**
     * 冒泡排序
     *
     * @param array 待排序的数组
     */
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped = false;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) { // compare adjacent elements
                    // swap array[j] and array[j+1]
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            if (!swapped) {
                // If no two elements were swapped in the inner loop, then break
                break;
            }
        }
    }

    public static void selectionSort(int[] array) {
        int n = array.length;
        // 总共要经过N-1轮比较
        for (int i = 0; i < n - 1; i++) {
            // 查找未排序数组中的最小元素
            int minIndex = i;
            // 每轮需要比较的次数
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the first element
            int temp = array[minIndex];
            array[minIndex] = array[i];
            array[i] = temp;
        }
    }

    /**
     * 插入排序
     * 注: 从数组第二个元素开始迭代, 将已排序好的左侧部分中 大于当前元素的数向右移动一位, 直到找到合适的位置插入当前元素
     *
     * @param array 待排序的数组
     */
    public static void insertionSort(int[] array) {
        int n = array.length;
        for (int i = 1; i < n; i++) {
            int key = array[i];
            int j = i - 1;
            //从已经排序的序列最右边的开始比较，找到比其小的数 到他们当前位置之前的一个位置
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j = j - 1;
            }
            array[j + 1] = key;
        }
    }
}
